#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

/**
 * PAT A 1139 First Contact
 */

enum Gender { MALE, FEMALE };

struct Vertex {
    std::string id;
    Gender gender;
    std::vector<int> to;

    Vertex(const std::string &rawId) {
        if (rawId.length() == 4) {
            id = rawId;
            gender = MALE;
        } else {
            id = rawId.substr(1);
            gender = FEMALE;
        }
    }
};

std::vector<Vertex> vertices;
std::unordered_map<std::string, int> rawIdToIdx;

int getIndex(const std::string &rawId) {
    if (rawIdToIdx.find(rawId) == rawIdToIdx.end()) {
        int idx = vertices.size();
        vertices.push_back(Vertex(rawId));
        rawIdToIdx.insert(std::make_pair(rawId, idx));
        return idx;
    } else 
        return rawIdToIdx[rawId];
}

int path[3];
std::vector<std::pair<std::string, std::string> > result;

void search(int target, bool same, int pathLen) {
    int prevIdx = path[pathLen - 1];
    Vertex &vert = vertices[prevIdx];
    Gender nextGen;
    if (!same && pathLen == 2)
        nextGen = Gender(1 - vert.gender);
    else
        nextGen = vert.gender;

    // Search target
    if (pathLen == 3) {
        for (int i = 0; i < vert.to.size(); i++) {
            int toIdx = vert.to[i];
            if (toIdx != target)
                continue;
            if (path[1] == target || path[2] == target)
                continue;
            result.push_back(std::make_pair(
                vertices[path[1]].id,
                vertices[path[2]].id
            ));
        }
        return;
    }

    // Search next friend
    for (int i = 0; i < vert.to.size(); i++) {
        int toIdx = vert.to[i];
        Vertex &toVert = vertices[toIdx];
        if (toVert.gender != nextGen)
            continue;
        if (pathLen == 2 && path[0] == toIdx)
            continue; // no cycle
        path[pathLen] = toIdx;
        search(target, same, pathLen + 1);
    }
}

int main() {
    // Read graph
    int nVerts, nEdges;
    scanf("%d %d", &nVerts, &nEdges);
    vertices.reserve(nVerts);
    for (int i = 0; i < nEdges; i++) {
        std::string fromId, toId;
        std::cin >> fromId >> toId;
        int fromIdx = getIndex(fromId);
        int toIdx = getIndex(toId);
        vertices[fromIdx].to.push_back(toIdx);
        vertices[toIdx].to.push_back(fromIdx);
    }

    int nCases;
    scanf("%d", &nCases);
    for (int i = 0; i < nCases; i++) {
        // Depth-first search the graph
        std::string fromId, toId;
        std::cin >> fromId >> toId;
        int fromIdx = getIndex(fromId);
        int toIdx = getIndex(toId);
        result.clear();
        path[0] = fromIdx;
        bool sameGender = vertices[fromIdx].gender == vertices[toIdx].gender;
        search(toIdx, sameGender, 1);

        // Sort and print result
        printf("%lu\n", result.size());
        std::sort(result.begin(), result.end());
        for (int i = 0; i < result.size(); i++)
            std::cout << result[i].first << ' ' << result[i].second << '\n';
    }

    return 0;
}